# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


from typing import *


class Solution:
    def constructFromPrePost(
        self, preorder: List[int], postorder: List[int]
    ) -> Optional[TreeNode]:

        post = {v: k for k, v in enumerate(postorder)}

        def f(l, r, L, R):
            if l > r:
                return None
            if l == r:
                return TreeNode(preorder[l])
            node = TreeNode(preorder[l])
            i = post[preorder[l + 1]]
            ls = i - L
            node.left = f(l + 1, l + ls + 1, L, i)
            node.right = f(l + ls + 2, r, i + 1, R - 1)
            return node

        n = len(preorder)
        return f(0, n - 1, 0, n - 1)


s = Solution()
print(s.constructFromPrePost([4, 2, 1, 3], [3, 1, 2, 4]))
print(s.constructFromPrePost([4, 2, 1, 3], [3, 1, 2, 4]))
